/*
 * 单链表的归并排序 : 分治思想
 * 归并排序: 将两个有序数列合并成一个有序数列，我们称之为“归并”。
 * 将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序
 * */

public class Main1 {
    public static void main(String[] args) {

        // 初始化一个链表
        ListNode head = new ListNode(4);
        ListNode node1 = new ListNode(3);
        ListNode node2 = new ListNode(8);
        ListNode node3 = new ListNode(1);
        ListNode node4 = new ListNode(2);
        ListNode node5 = new ListNode(5);
        ListNode node6 = new ListNode(13);
        head.setNext(node1);
        node1.setNext(node2);
        node2.setNext(node3);
        node3.setNext(node4);
        node4.setNext(node5);
        node4.setNext(node5);
        node5.setNext(node6);
        head.print();  // 4 3 8 1 2 5 13
        mergeSort(head).print();

    }


    // 归并排序, 递归
    public static ListNode mergeSort(ListNode head){
        if(head==null || head.next == null) return head; // 递归出口
        ListNode secondHead = splitList(head);
        return mergeTwoList(mergeSort(head),mergeSort(secondHead));
    }

    // 合并两个有序链表
    public static ListNode mergeTwoList(ListNode p1,ListNode p2){
        ListNode dummy = new ListNode(-1); // 假节点
        ListNode flag = dummy;
        while(p1 != null && p2 != null){
            if(p1.value <= p2.value){
                flag.next = p1;
                p1 = p1.next;
            }else{
                flag.next = p2;
                p2 = p2.next;
            }
            flag = flag.next;
        }

        if(p1!=null) flag.next = p1;
        if(p2!=null) flag.next = p2;
        return dummy.next;
    }

    // 利用快慢指针把一个链表一分为二
    public static ListNode splitList(ListNode head){
        ListNode first = head;
        ListNode slow = head;

        while(first.next != null && first.next.next != null){
            first = first.next.next;
            slow = slow.next;
        }

        ListNode secondHead = slow.next;  // 找打后半段链表的头节点
        slow.next = null;   // 将链表一份为二
        return secondHead;
    }

}



